package com.chocho.queue;

public class ArrayQueueDemo {
    public static void main(String[] args) {
        try {
            //创建一个队列
            ArrayQueue queue = new ArrayQueue(3);
//            System.out.println("初始化队列内容");
//            queue.showQueue();

            //输入数据
            queue.addQueue(10);
            queue.addQueue(20);
            queue.addQueue(30);
            //队满插入数据
            queue.addQueue(40);
            queue.showQueue();

            //获取队头数据
            System.out.printf("\n查看队头数据:%d", queue.headQueue());
            System.out.printf("\n获取队头数据:%d", queue.getQueue());
            System.out.printf("\n查看队头数据:%d", queue.headQueue());

        }catch (Exception e){
            e.printStackTrace();
        }
    }
}

/**
 * 关键点：
 * 1.队头在数组地址低位，队尾在数据地址高位
 * 2.队头始终在队头数据前一个位置，队尾始终在队尾数据的位置，即(front,rear]为队列范围；
 * 因此，front初始化为-1，rear初始化为-1，才能代表队列为空
 * 3.队满判断，队列满时说明到达最大容量，即不能再往队列插入数据，rear不能再增长，rear==maxSize-1
 * 4.队空判断，队列空时，要保证(front,rear]的集合为空，即front==rear
 * 5.队列中有效数据个数：队尾-队头，rear-front
 *
 * 问题分析：（上面这种设计方式存在问题）
 * 通过持续监控运行过程中queue的内容变化，可知，当不断出队，出队后的空间再也不能使用，最终在出队maxSize
 * 次后，虽然实际上有存储空间，但是队列已经无法再插入数据；其实可以理解为队列在持续后移，只不过碰到maxSize
 * 的界限无法后移了，因此需要将空间从逻辑上扩展为无限的，即采用环形队列：当无法入队时，重新利用前面废弃的空间
 *
 * *实现环形的方法：数组 % 取模运算
 */
class ArrayQueue{
    private int maxSize; //数组最大容量
    private int front; //队头下标，数据输出端
    private int rear; //队尾下标，数据输入端
    private int[] arr; //队列数据，模拟队列

    /**
     * 创建队列
     */
    public ArrayQueue(int maxSize){
        this.maxSize = maxSize;
        this.front = -1; //队头默认在-1位置，即没有数据存储在队列中，-1则指向队头元素位置
        this.rear = -1; //队尾默认在-1位置，-1指向队尾数据
        this.arr = new int[maxSize]; //初始化队列
    }

    /**
     * 判断队满
     */
    public boolean isFull(){
        return this.rear == this.maxSize - 1;
    }

    /**
     * 判断队空
     */
    public boolean isEmpty(){
        return this.rear == this.front;
    }

    /**
     * 向队列添加数据
     * @param data
     */
    public void addQueue(int data){
        //判断队满
        if(isFull()){
            System.out.println("队列满，不能添加数据");
            return;
        }
        rear++;
        arr[rear] = data;
    }

    /**
     * 获取队头数据
     * @return
     */
    public int getQueue() throws Exception {
        //判空
        if(isEmpty()){
            throw new Exception("队列为空，不能获取数据");
        }
        front++;
        return arr[front];
    }

    /**
     * 显示队头数据
     * @return
     */
    public int headQueue() throws Exception {
        //判空
        if(isEmpty()){
            throw new Exception("队列为空，不能获取数据");
        }
        return arr[front + 1];
    }

    /**
     * 显示队列数据
     */
    public void showQueue() throws Exception {
        if(isEmpty()){
            throw new Exception("队列为空，不能获取数据");
        }

        System.out.print("[");
        for (int i = 0; i < arr.length; i++){
            System.out.printf("[%d]=%d\t", i, arr[i]);
        }
        System.out.print("]");
    }
}